1. Field of the Invention
The present invention relates to computer control programs, and more particularly relates to that feature of such control programs that controls the transfer of pages of data between storage and memory for the purpose of memory management.
2. Background Art
Memory management is a necessary function in large mainframe control programs, particularly those in which multiple computing entities with multiple tasks may be created and run simultaneously. The real memory of even a large mainframe computer system may be insufficient to service every task running in the system at a particular time. Accordingly, control programs for such mainframes employ an expedient known as "paging".
Control programs implementing manage real memory in units of fixed size, called pages, typically 4 kilobytes. Real memory is divided into real page frames each able to hold one page of data. The programs and data associated with the tasks being executed are organized into pages. Pages associated with a task can be assigned to a real page frame and thus be available for use by the task, or they can be "paged out" to a paging device or a direct access storage device (DASD). The pages from all active computing entities and tasks compete for available page frames. Only "active" pages should remain in memory for utilization by the processor as it executes its tasks on the computer system. When the number of page frames available for allocation to new tasks falls below a threshold value those pages which, according to given criteria, are not frequently referenced, or which have not been referenced for some predetermined amount of time, are transferred to storage, thus freeing up that page frame for allocation to a page of data needed for a task demanding execution by the processor.
Page management routines use a core table to keep track of real memory page frames. Each page frame has an entry in the core table that contains pointers indicating the status and ownership of the corresponding real page. A core table entry may appear on either of two lists indicating its availability for paging: the free list; and the flush list. The free list contains those page frames immediately available for allocation while the flush list contains those page frames available for allocation after paging out the data currently in the page frames.
Control program memory management seeks to allocate system page frames of real memory to satisfy the demands for virtual pages made by the computing entities or tasks. The control program seeks to insure that the set of virtual storage pages that are resident in real page frames represent those pages that are most likely to be used. If this is not the case, the processor must spend considerable overhead time in paging out the unused pages and paging in the required pages. Thus, the first problem of memory management is to determine which pages are most likely to be used or conversely which pages are "least recently used".
A second problem is to efficiently manage the page in and page out activity. Paging out involves the transfer of pages from the high speed memory to a lower speed device such as a paging device or DASD. The slower speed of the paging device or DASD introduces inefficiencies if the pages are paged out one at a time. System overhead can be reduced if a group of pages can be paged out in one operation. Swapping relates to the paging in or paging out of groups of pages. Logical swapping is a process of creating lists of pages that are available to be written to the paging media. Physical swapping provides for better paging media use by writing and reading pages in groups.
The computer keeps a record of where in storage the paged out page actually resides, so that if that page is required for a task subsequently demanding execution it can be retrieved from storage and placed back in a memory page frame for use in the execution of that task.
The prior art has approached the implementation of paging in two ways. One is the Local Least Recently Used ("LLRU") approach with swapping. This involves periodically determining which pages of an individual user or computing entity have been referenced in a given immediately preceding period of computer resource allocation to a given user, or time slice, and grouping these "old" pages into "swap sets" for subsequent transfer to storage. Pages which have not been referenced in the given immediately preceding period or time slice are paged individually. Swap sets are transferred back to memory when any one page of the set is demanded. The idea is that since they were all referenced previously in a given time slice, there is a good likelihood they will be needed together again. Transferring pages in groups, or sets, is more efficient than transferring individual pages.
The other approach is the Global Least Recently Used ("GLRU") approach. This involves determining, on a system-wide basis, which pages in memory have not been recently referenced without regard to user or time slice considerations. The pages not recently referenced are then paged out as free page frames are required for allocation.
The GLRU approach has the advantage of simplicity. That is, it does not concern itself with considerations such as the owning user or its state. Similarly, it optimizes use of the memory for the system as a whole, by basing its paging decisions on system wide page usage rather than user dependent considerations. Also, since it is demand driven, that is, the time it spends looking for unreferenced pages to make room for new pages is dependent upon the actual demand for page frames, it adds overhead in proportion to the needs of the system. The rate at which pages in memory are checked to determine whether they have been re-referenced (and thus should be retained) automatically increases as a function of demand. In contrast, LLRU determines page references periodically, e.g. at the end of each timeslice, regardless of demand. LLRU has the further disadvantage of causing paging out of data at the end of a period when a lightly loaded system may have no need for the page frames. This can cause unnecessary paging overhead.
However, GLRU inherently selects its pages one at a time, so the benefits of swapping are not obtained. That is, pages are not grouped together for removal from and subsequent return to memory in some kind of efficiency-oriented scheme, such as relation by user, and likelihood of use together. Single page input and output is much less efficient than the swapping of groups. But since GLRU selects pages from the system wide list (the core table), they are selected in essentially random order. Swapping sets of unrelated pages would not achieve the desired benefits since the unrelated groups are not likely to be referenced again as a set.
The local LRU approach easily provides the benefits of swapping, because the system selects pages for swapping by looking at one user at a time a "local" view, resulting in user dependent organization of the pages in swap sets. The major disadvantage of local LRU is that it is not "demand driven". That is, it provides relatively fixed overhead in its formation of swap sets, whether or not the page frames freed by swapping are actually required. Further, the interval over which the reference decision is made is not tied to system demand nor recognition of program behavior that would influence the required time interval. The local focus of local LRU means that the paging activity of the entire system is not optimized. Thus, one user or computing entity can retain pages on a local basis which, in a global sense should have been paged out.
Thus there is a need for an improved method of paging to provide a more efficient memory management and paging system that minimizes the overhead requirements imposed by such a system through efficient use of processor and input and output resources.